package com.cat.dataStructure;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/lexicographically-minimum-string-after-removing-stars/description/
 * @create 2025/9/8 19:09
 * @since JDK17
 */

public class Solution61 {
    public String clearStars(String s) {
        int n = s.length();
        Deque<Integer>[] stacks = new ArrayDeque[26];
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) != '*') {
                stacks[s.charAt(i) - 'a'].add(i);
            } else {
                for (int j = 0; j < 26; j++) {
                    if (stacks[j].size() != 0) {    // 删除最后面的
                        stacks[j].pop();
                        break;
                    }
                }
            }
        }
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for (int i = 0; i < 26; i++) {
            while (!stacks[i].isEmpty()) {
                q.add(stacks[i].pop());
            }
        }
        char[] ans = new char[q.size()];
        for (int i = 0; !q.isEmpty(); i++) {
            ans[i] = s.charAt(q.poll());
        }
        return new String(ans);
    }
}
